/**
 * Created by ospip on 2017/9/15.
 * Copyright (c) 2017 LLAP. All rights reserved.
 */
public class Prime {
    private byte n[];
    private int nl, nr;
    private long beginTime, endTime, costTime;
    public Prime(int l, int r) {                // [1, 1413000000], 70602184, 12.300823942s
        beginTime = System.nanoTime();
        nl = l; nr = r;
        n = new byte[r + 1];
        n[2] = 1;
        for (int i=3; i<=r; i+=2) n[i]=1;
        for (int i=3; i<=Math.sqrt(r); i+=2) {
            if (n[i]==1) {
                for (int j=i*i, m=i; j<=r; m+=2, j=i*m) {
                    if (n[j]==1) {
                        n[j]=0;
                    }
                }
            }
        }
        endTime = System.nanoTime();
        costTime = endTime - beginTime;
    }
    public int count() {
        int cnt = 0;
        for (int i = nl; i <= nr; i++) {
            if (n[i] == 1) ++cnt;
        }
        return cnt;
    }
    public int leftBound() {
        return this.nl;
    }
    public int rightBound() {
        return this.nr;
    }
    public double duration() {
        return (double)costTime / 1000 / 1000 / 1000;
    }
    public static void main(String[] args) {
        Prime p = new Prime(1, 500000000);  //Surface Pro 4 m3: [1, 700000000], 9.7435s
        System.out.println("在[" + p.leftBound() + ", " + p.rightBound() + "]范围内共找到" + p.count() + "个质数");
        System.out.println("用时" + p.duration() + "秒");
    }
}
